package sort.quicksort;

import sort.generator.ArrayGenerator;
import sort.helper.SortingHelper;

import java.util.Random;

/**
 * @author XY
 * @version 1.0
 * @date 2021/9/13 11:44
 * @Description
 */
public class Main {
    public static void main(String[] args) {

        int n =100000;
//        Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
//        SortingHelper.sortTest("QuickSort",arr);
//        Integer[] arr1 = ArrayGenerator.generateRandomArray(n, n);
//
//        SortingHelper.sortTest("QuickSort2",arr1);
        Integer[] arr2 = ArrayGenerator.generateRandomArray(n, n);

        SortingHelper.sortTest("QuickSort3",arr2);
        int[] arr4= {3,2,1,5,6,4};

        Solution solution = new Solution();
        solution.findKthLargest(arr4,2);
    }


    static class Solution {
        public int findKthLargest(int[] nums, int k) {
            return selectK(nums,nums.length-k,0,nums.length-1);
        }

        private int selectK(int[] nums, int k,int l, int r){
            int p = partition2(nums,l,r);
            if(p==k){
                return nums[p];
            }
            else if (k<p){
                return selectK(nums,k,l,p-1);
            }
            else{
                return selectK(nums,k,p+1,r);
            }
        }

        private int partition2(int[] arr,int l,int r){
            //增加随机化，避免遇到有序数组排序时间过长
            int p = l+new Random().nextInt(r-l+1);
            swap(arr,l,p);
            int i = l+1,j=r;
            while(true){
                while(i<=j && arr[i]<arr[l]){
                    i++;
                }
                while(j>=i && arr[j]>arr[l]){
                    j--;
                }
                if(i>=j){
                    break;
                }
                swap(arr,i,j);
                i++;
                j--;
            }
            swap(arr,l,j);
            return j;
        }

        private  void swap(int[] arr,int a,int b){
            int temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }

    }
}
